The analysis and the handling of multigraphs in an efficient manner is becoming a necessity given the growing volume of network or multigraph-structured data.
Methods for managing data in multigraph form are known, although they have limitations with respect to the efficient handling and storage capacity of this type of data. Specifically, these methods do not allow efficiently managing data in multigraph form when the size of such data grows significantly. This occurs because the data structures used do not favor the efficient performance of some of the most common operations of multigraphs and, specifically, because: 1) data structures do not allow quickly accessing information as is required by said operations and 2) data structures are not optimized to take into account that the memory capacity is limited. Examples of said operations are: searching for patterns in a multigraph, scanning the multigraph through the relationship of a vertex with its neighbors, finding the diameter of the multigraph, etc.
The use of systems based on traditional data models such as the relational model for the management of multigraphs does not meet the necessary requirements for constructing an efficient system which allows consulting and handling said multigraphs when they are very large. In the relational model it is considered that the data are stored in records which are organized in relationships. While this organization favors consultations in which the most important thing is the information stored in each record, it does not favor some typical consultations of multigraphs relating to the analysis of the relationship between entities.
The use of specific representation systems for multigraphs such as incidence matrices allows efficiently handling multigraphs, but they require that the entire multigraph can be handled in memory and have serious restrictions when the elements of the multigraph contain associated attributes, or when more information besides the actual structure of the multigraph must be stored.
A system is therefore needed for representing generic multigraphs with attributes allowing the consultation and handling of said multigraphs in an efficient manner and without requiring that the entire multigraph fit in the memory available in the system.
The “DEX: High-Performance Exploration on Large Graphs for Information Retrieval (CIKM'07, Nov. 6-8, 2007 Lisbon, Portugal)” discloses a high performance graph database querying system that allows for the integration of multiple data sources. Features disclosed in this paper in common with the current invention are included in the preamble of claim 1.